package 快速排序;

import java.util.Arrays;
import java.util.Stack;

public class quicksort3 {
    public static  int partition(int[] array,int start,int end) {
        //挖坑法
        int tmp=array[start];
        while(start<end) {
            while(start<end && array[end]>=tmp) {
                end--;
            }
            //end下标遇到了 小于 tmp的值
            array[start]=array[end];
            while(start<end && array[start]<=tmp) {
                start++;
            }
            //start 下标遇到了 大于tmp 的值
            array[end]=array[start];
        }
        array[start]=tmp;
        return start;
    }

    public static void quickSort3(int[] array) {
        Stack<Integer> stack=new Stack<>();

        int left=0;
        int right=array.length-1;
        int pivot=partition(array,left,right);
        if(pivot>left+1) {
            //左边有两个元素
            stack.push(left);
            stack.push(pivot-1);
        }

        if(pivot<right-1) {
            //右边有两个元素
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()) {
            right=stack.pop();
            left=stack.pop();

            pivot=partition(array,left,right);
            if(pivot>left+1) {
                //左边有两个元素
                stack.push(left);
                stack.push(pivot-1);
            }

            if(pivot<right-1) {
                //右边有两个元素
                stack.push(pivot+1);
                stack.push(right);
            }
        }

    }

    public static void main(String[] args) {
        int[] array={12,5,9,34,0,33,6,55};
        quickSort3(array);
        System.out.println(Arrays.toString(array));
    }



}
